/*
	Copyright (c) 2009-2011, Stefan Webb.

	This file is part of SimpleML. Please read the file "license.txt", 
	which contains the conditions under which this software is distributed.
*/

/*!
	\file minheap.h
	\author Stefan Webb
	\brief Definition of the MinHeap class template
*/

#ifndef MINHEAP_H
#define MINHEAP_H

//#include "stdafx.h"

/*! \brief Class for minheap. */
template <class T = unsigned int> class MinHeap : public Bucket<T>
{
public:
	/*! \brief Default constructor. */
	MinHeap();

	/*! \brief Constructor with capacity specified.
		\param Capacity of minheap. */
	MinHeap(unsigned int capacity);

	/*! \brief Insert an element into the minheap. 
		\param element Element to insert into minheap. */
	void insert(T element);

	/*! \brief Extract the minimum element.
		\return Minimum element. */
	T extract();

	/*! \brief Return but do not extract minimum element. 
		\return Minimum element. */
	T& minimum();

protected:
	/*! \brief Assuming children of index node satisfy minheap property, move 
		indexed node so that the subtree at index satisifies minheap property.
		\param index Node from which to heapify. */
	void heapify(unsigned int index);

	/*! \brief Calculate parent of node.
		\param i Node for which to calculate parent.
		\return Parent of specified node. */
	unsigned int parent(unsigned int i);

	/*! \brief Calculate left child of node.
		\param i Node for which to calculate left child.
		\return Left child of specified node. */
	unsigned int left(unsigned int i);

	/*! \brief Calculate right child of node.
		\param i Node for which to calculate right child.
		\return Right child of specified node. */
	unsigned int right(unsigned int i);
};

/* Default constructor. */
template <class T> MinHeap<T>::MinHeap() {}

/* Constructor with capacity specified. */
template <class T> MinHeap<T>::MinHeap(unsigned int capacity) : Bucket(capacity) {}

/* Insert an element into the minheap. */
template <class T> void MinHeap<T>::insert(T element)
{
	// Initialize position of last element
	unsigned int thisNode = size_, parentNode = 0;
	T tempElement;

	// Add the element to the end of the heap.
	add(element);

	// While it is less than its parent, move it back
	while (true) {
		// If we are at the top then break
		if (thisNode == 0)
			break;

		// Otherwise, fetch parent
		parentNode = parent(thisNode);

		// If the parent node is smaller than this node then break
		if (array_[parentNode] < array_[thisNode])
			break;

		// Otherwise move node back one
		tempElement = array_[parentNode];
		array_[parentNode] = array_[thisNode];
		array_[thisNode] = tempElement;
		thisNode = parentNode;
	}
}

/* Extract the minimum element. */
template <class T> T MinHeap<T>::extract()
{
	// If no elements then throw exception
	if (!size_)
		(error << L"Cannot extract element from empty heap.").exception();

	// Get minimum and move last element to first
	T tempElement = minimum();
	minimum() = pop();

	// Heapify and return minimum
	heapify(0);
	return tempElement;
}

/* Return but do not extract minimum element. */
template <class T> T& MinHeap<T>::minimum()
{
	return array_[0];
}

/* Heapify. */
template <class T> void MinHeap<T>::heapify(unsigned int index)
{
	// Initialize left and right child indices
	unsigned int leftChild, rightChild, smallest;
	T tempElement;

	// Loop until minheap property is established
	while (true) {
		// Initialize indices
		leftChild = left(index);
		rightChild = right(index);
		smallest = index;

		// If there is a left child then compare to index
		if (leftChild < size_) {
			if (array_[leftChild] < array_[smallest])
				smallest = leftChild;
		}

		// If there is a right child then compare to index
		if (rightChild < size_) {
			if (array_[rightChild] < array_[smallest])
				smallest = rightChild;
		}

		// Only break when the smallest one is the index
		if (smallest == index)
			break;

		// Otherwise swap the smallest one and the index
		tempElement = array_[index];
		array_[index] = array_[smallest];
		array_[smallest] = tempElement;
		index = smallest;
	}

}

/* Calculate parent of node. */
template <class T> unsigned int MinHeap<T>::parent(unsigned int i)
{
	return i >> 1;
}

/* Calculate left child of node. */
template <class T> unsigned int MinHeap<T>::left(unsigned int i)
{
	return 2 * i;
}

/* Calculate right child of node. */
template <class T> unsigned int MinHeap<T>::right(unsigned int i)
{
	return 2 * i + 1;
}

#endif